from typing import List, Optional

from python.mypackage import TreeNode


class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        def recur(in_left, in_right):
            if in_left > in_right:
                return None
            #后续列表最后一个节点为根节点
            val = postorder.pop()
            root = TreeNode(val)

            index = dic[val]
            root.right = recur(index + 1, in_right)
            root.left = recur(in_left, index - 1)
            return root

        dic = {val:idx for idx, val in enumerate(inorder)}
        return recur(0, len(inorder) - 1)